This invention relates to integrated circuits, particularly programmable logic devices or field programmable gate arrays (FPGAs). More particularly, this invention relates to compression methods for reducing the size of a bitstream used to program an FPGA.
Field programmable gate arrays (FPGAs) are configured to perform particular functions by loading a stream of bits, or bitstream, into a memory that controls configuration of configurable logic blocks (CLBs). Each CLB includes configurable logic, horizontal and vertical line segments that connect across adjacent cells to form interconnect lines, and a routing or switching structure to selectively connect the logic to the line segments.
It is sometimes desirable to change the functionality of the FPGA by reconfiguring some or all of the logic blocks. In the past, reconfiguration involved reprogramming the entire FPGA by loading a complete new bitstream into the FPGA to reconfigure all of the CLBs.
As FPGAs have grown rapidly in size, partial reconfiguration techniques have evolved to enable reconfiguration of selected portions of the FPGA without affecting other portions of the same FPGA. Due to the architecture of FPGAs, however, partial reconfiguration has been traditionally limited to reconfiguring entire columns of memory for controlling CLBs.
FIG. 1 shows an FPGA 20 to illustrate the limitations of conventional partial reconfiguration. The FPGA 20 has an array of tiles, each tile comprising configurable logic and related interconnect, which are collectively referred to as a configurable logic block (CLB) 22. For illustration purposes, only a few CLBs are shown in FIG. 1 and only a few of the interconnect lines have been drawn. Typically, an FPGA 20 is implemented with thousands of repeatable CLBs 22, each having many horizontal and vertical line segments. Young, Chaudhary and Bauer in U.S. Pat. No. 5,914,616 describe such a structure in more detail, and this patent is incorporated herein by reference.
Each CLB 22 has configurable logic, horizontal and vertical line segments that connect across adjacent cells to form interconnect lines, and a routing or switching structure to selectively connect the logic to the line segments. configuration of the logic and connection between line segments is controlled by a configuration memory, into which a configuration is loaded for enabling the logic and interconnect lines to perform a desired function. In some FPGAs, data in the configuration memory is loaded by addressing sections of configuration memory on address lines and applying data to data lines. In some FPGAs, a frame of configuration data is fed serially into a shift register, then shifted in parallel to an addressed column of configuration memory cells. Vertical wires form address lines, as represented by address lines 24, that generally span the height of the FPGA. Horizontal wires form data lines, as represented by data lines 26, that usually span the width of the FPGA.
In the FPGA of FIG. 1, configuration data from the bitstream is placed onto the data lines 26 by a shift register 28. The bitstream contains frames of data, where each frame fills the shift register 28 and is used to program one column of memory cells accessed by a corresponding address line. As an example, the shift register 28 might hold a frame consisting of several thousands bits. The bitstream also contains commands to load a corresponding data frame into the shift register and once loaded, commands to select the appropriate address line associated with the data frame.
After an entire frame is loaded into the shift register 28, the data bits may be temporarily transferred to a shadow register 30 so that the shift register 28 is free to begin receiving the next frame of data. An address line is selected to transfer the data from the shadow register 30 via the data lines 26 into selected memory cells of the CLBs. This process is repeated for all address lines 24 to fully program the CLBs 22 on the FPGA 20.
Using conventional methods, FPGA 20 can be partially reconfigured by shifting data bits into the shift register 28 and selecting only the address lines 24 of the CLBs 22 that are being reprogrammed. Unfortunately, since the address lines 24 span entire columns of CLBs 22, all of the CLBs connected by the common address lines 24 are reconfigured, whether or not the programmer wants to change all blocks. This is represented pictorially in FIG. 1 as a partial reconfiguration zone 32.
As FPGAs continue to increase in size and complexity, it would be desirable and advantageous to partially reconfigure smaller sections of the FPGA that include less than all of the CLBs connected to a common address line. Accordingly, there is a need for an improved process or architecture that enables partial reconfiguration of selectable CLBs on the FPGA.
Another problem resulting from the FPGA""s rapid growth in size concerns the enormously increasing length of the bitstream used to program the FPGA. Clock speeds used to shift the bitstreams into an FPGA have increased, but less dramatically, thus increasing the length of time required to load the bitstream into the FPGA.
In an effort to address this problem, some FPGA architectures dedicate multiple data pins to receive the bitstream, rather than a single pin as used in earlier design generations. This improvement, however, costs package pins, and there remains a desire to further reduce the time required to configure or reconfigure an FPGA.
One way to improve the speed of FPGA configuration is to reduce the size of the bitstream. Unfortunately, standard compression algorithms used in other signal processing environments are not effective for FPGA bitstreams because they require large amounts of memory. Conventional compression algorithms that do not require large amounts of memory, such as run length encoding (RLE), have not proven effective with typical bitstream data. Accordingly, there remains a need to compress the size of the bitstream in a way that reduces the length of time required to load the bitstream into the FPGA.
This invention relies on an FPGA architecture that can reconfigure a part of the FPGA at a resolution of one word. In one embodiment, the method enables partial reconfiguration of selectable configurable logic blocks (CLBs) connected to one or more address lines, without affecting other CLBs connected to the same address lines.
This invention concerns a system and method to reduce the size of the bitstream used in configuring or reconfiguring the FPGA. The compression method evaluates the configuration data and identifies, for a given frame, the most similar frame in the configuration data. The most similar frame may be an identical frame, in which all words or bits are the same, or a similar frame in which only a few bits or words differ between them. The compression method reorganizes the frames within the bitstream to group the similar frames so that the amount of data bits being changed from one frame to the next is minimized. Duplicated words/bits that do not change from one frame to the next are removed, leaving only their corresponding commands and addresses for selecting the address lines that are intended to program cells with this data.
To enable loading of individual words, as opposed to whole frames, the FPGA is implemented with an addressable data register instead of a conventional shift register. Individual words from a data frame of the bitstream can be loaded directly into the data register at an addressed location.